/*
 * @lc app=leetcode.cn id=139 lang=cpp
 *
 * [139] 单词拆分
 */
#include <string>
#include <unordered_set>
#include <vector>

using std::string;
using std::unordered_set;
using std::vector;

// @lc code=start
class Solution
{
  public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        unordered_set<string> word_set;
        for (const auto &word : wordDict) {
            word_set.insert(word);
        }

        /* dp[i] 表示从s[0,i]这个子字符串能在字典中找到 */
        vector<bool> dp(s.size() + 1, false);
        /* 空字符串，假设能找到 */
        dp[0] = true;

        /* 遍历s的每个字符 */
        // leetcode, leet,code
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                /* 如果dp[j]能找到，且s[j, i]也能找到，那么s[0,i]也都能在wordDict中找到 */
                if (dp[j] && word_set.count(s.substr(j, i - j))) {
                    /* 发现s[0,i]能找到的时候，直接break，不必再继续寻找了 */
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};
// @lc code=end
